#include <stdio.h>
#include <memory.h>

int n, k, wood[ 5001 ], f[ 5001 ][ 1001 ];
int hash( int a, int b )
{
    return ( wood[ a ] - wood[ b ] ) * ( wood[ a ] - wood[ b ] );   
}   
int min( int a, int b )
{
    return ( a < b ? a : b );
}
void work( )
{   
    int i, j;  
    for ( i = 0; i <= n; i++ )   
        for( j = 0; j <= k; j++ )
            f[ i ][ j ] = 10000000;   
    for ( i = 0; i < n; i++ )   
        f[ i ][ 0 ] = 0;
        for( i = n - 2; i >= 0; i-- )
            for( j = 1; j <= k; j++ )
        {
                if   ( j * 3 > ( n - i ) )
                break;
                f[ i ][ j ] = min(f[ i + 1 ][ j ], f[ i + 2 ][ j - 1 ] + hash( i, i + 1 ) );
        }
}   

int   main()   
{   
    int t, i;
    scanf("%d", &t);
    while( t-- )
    {
        scanf("%d%d", &k, &n);
        k += 8;
        memset( wood, 0, sizeof( wood ) );
        for( i = 0; i < n; i++ )
            scanf("%d", &wood[ i ]);
        work( );
        printf("%d\n", f[ 0 ][ k ]);
    }
    return 0;
}
